"""
654. 最大二叉树 - 分治算法实现

两种解法：
1. 递归分治法：直观解法，时间复杂度O(n²)
2. 单调栈法：优化解法，时间复杂度O(n)
"""

from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
    def __repr__(self):
        return f"TreeNode({self.val})"

class Solution:
    def constructMaximumBinaryTree_recursive(self, nums: List[int]) -> Optional[TreeNode]:
        """
        方法一：递归分治法（直观解法）
        
        算法思路：
        1. 找到数组中的最大值作为根节点
        2. 递归构建左子树（最大值左侧的子数组）
        3. 递归构建右子树（最大值右侧的子数组）
        
        时间复杂度：O(n²) - 每次需要遍历数组找最大值
        空间复杂度：O(n) - 递归栈深度
        """
        if not nums:
            return None
        
        # 找到最大值及其索引
        max_val = max(nums)
        max_idx = nums.index(max_val)
        
        # 创建根节点
        root = TreeNode(max_val)
        
        # 递归构建左右子树
        root.left = self.constructMaximumBinaryTree_recursive(nums[:max_idx])
        root.right = self.constructMaximumBinaryTree_recursive(nums[max_idx+1:])
        
        return root
    
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        """
        方法二：单调栈优化法（推荐解法）
        
        算法思路：
        1. 维护一个单调递减栈
        2. 遇到更大元素时，弹出栈中较小元素作为当前节点的左子树
        3. 当前节点成为栈顶元素的右子树
        
        时间复杂度：O(n) - 每个元素最多入栈出栈一次
        空间复杂度：O(n) - 栈的空间
        """
        stack = []
        
        for num in nums:
            cur = TreeNode(num)
            
            # 当栈不为空且栈顶元素小于当前元素时
            # 弹出栈顶元素作为当前节点的左子树
            while stack and stack[-1].val < num:
                cur.left = stack.pop()
            
            # 如果栈不为空，当前节点成为栈顶元素的右子树
            if stack:
                stack[-1].right = cur
            
            # 当前节点入栈
            stack.append(cur)
        
        # 栈底元素就是根节点
        return stack[0] if stack else None

def print_tree_inorder(root):
    """中序遍历打印二叉树"""
    if not root:
        return []
    result = []
    result.extend(print_tree_inorder(root.left))
    result.append(root.val)
    result.extend(print_tree_inorder(root.right))
    return result

def print_tree_preorder(root):
    """前序遍历打印二叉树"""
    if not root:
        return []
    result = [root.val]
    result.extend(print_tree_preorder(root.left))
    result.extend(print_tree_preorder(root.right))
    return result

def tree_to_list(root):
    """将二叉树转换为层序遍历的列表表示（包含null）"""
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    
    # 移除末尾的None
    while result and result[-1] is None:
        result.pop()
    
    return result

# 测试函数
def test_algorithm():
    """测试算法正确性"""
    solution = Solution()
    
    # 测试用例
    test_cases = [
        [3, 2, 1, 6, 0, 5],  # 示例1
        [3, 2, 1],           # 示例2
        [1],                 # 单元素
        [1, 2, 3, 4, 5],     # 递增序列
        [5, 4, 3, 2, 1],     # 递减序列
    ]
    
    for i, nums in enumerate(test_cases, 1):
        print(f"\n测试用例 {i}: {nums}")
        
        # 递归方法
        root1 = solution.constructMaximumBinaryTree_recursive(nums.copy())
        result1 = tree_to_list(root1)
        
        # 单调栈方法
        root2 = solution.constructMaximumBinaryTree(nums.copy())
        result2 = tree_to_list(root2)
        
        print(f"递归方法结果: {result1}")
        print(f"单调栈方法结果: {result2}")
        print(f"结果一致: {result1 == result2}")

if __name__ == "__main__":
    test_algorithm()
